package org.example.Backtracking_algorithm;

import java.util.Arrays;
import java.util.HashSet;

public class Solve_Sudoku {
    public static void main(String[] args) {
        //解数独

        //编写一个程序，通过填充空格来解决数独问题。
        //数独的解法需 遵循如下规则：
        //数字 1-9 在每一行只能出现一次。
        //数字 1-9 在每一列只能出现一次。
        //数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
        //数独部分空格内已填入了数字，空白格用 '.' 表示。
        char[][] board = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
        };
        solveSudoku(board);
    }
    public static void solveSudoku(char[][] board) {
        get(board);
        System.out.println(Arrays.deepToString(board));
    }
    public static boolean get(char[][] board){
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j]!='.') continue;
                for (char k = '1'; k <='9'; k++) {
                    if (isAvailable(i,j,k,board)){
                        board[i][j] = k;
                        //System.out.println(board[i][0]+" "+board[i][1]+" "+board[i][2]+" "+board[i][3]+" "+board[i][4]+" "+board[i][5]+" "+board[i][6]+" "+board[i][7]+" "+board[i][8]);
                        if (get(board)){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    public static boolean isAvailable(int i,int j,char k,char[][] board){
        for (int l = 0; l < 9; l++) {
            if (board[i][l]==k || (board[l][j]==k)) return false;
        }

        int startRow = (i/3)*3; //计算起始行
        int startCol = (j/3)*3; //计算起始列
        for (int l = startRow; l < startRow+3; l++) {
            for (int m = startCol; m < startCol + 3; m++) {
                if (board[l][m]==k) return false;
            }
        }
        return true;
    }
}
